package com.blue.basic.data.sort;

/**
 * 将给定的单链表L： L 0→L 1→…→L n-1→L n,
 * 重新排序为： L 0→L n →L 1→L n-1→L 2→L n-2→…
 * 要求使用原地算法[现有的算法结构]，并且不改变节点的值
 * 例如：
 * 对于给定的单链表{1,2,3,4}，将其重新排序为{1,4,2,3}
 * 对于给定的单链表{1,2,3,4,5,6}，将其重新排序为{1,6,2,5,3,4}
 *
 * @author liulei, lei.liu@htouhui.com
 * @version 1.0
 */
public class LinkedList {
    public static void main(String[] args) {
        int oldCapacity=10;
        oldCapacity = 10 + (oldCapacity >> 1);
        System.out.println(oldCapacity);
    }
    public void reorderList(ListNode head) {
        if (head.next == null || head.next.next == null) {
            return;
        }
        //思路：找到中间节点，拆成2个链表后，对两个链表使用前插法合并成一个链表
        ListNode midNode = getMidNode(head);
        //反转链表2
        ListNode after = midNode.next;
        midNode.next = null;
        ListNode pre = null;
        while(after != null){
            ListNode temp = after.next;
            after.next = pre;
            pre = after;
            after = temp;
        }
        //合并两个链表
        ListNode first = head;
        after = pre;
        while(first != null && after != null){
            ListNode ftemp = first.next;
            ListNode aftemp = after.next;
            first.next = after;//first->
            first = ftemp;
            after.next = first;
            after = aftemp;
        }
    }

    /**
     * 快慢节点遍历法，查找中间节点
     *
     * @param head 头节点
     * @return 中间节点，偶数节点会选择第一个节点
     */
    ListNode getMidNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}
//题目给定的类
class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}